Merkle Tree [English]

InterPARES Definition

No definition in earlier IP projects. ITrust definition not yet developed.

Other Definitions

  • Bitcoin Developer Glossary 2017 (†791 s.v. "Merkle tree"): A tree constructed by hashing paired data (the leaves), then pairing and hashing the results until a single hash remains, the merkle root. In Bitcoin, the leaves are almost always transactions from a single block.
  • BlockchainHub Glossary (†807 s.v. "Merkle tree"): The basic idea behind Merkle tree is to have some piece of data that is linking to another. You can do this by linking things together with a cryptographic hash. The content itself can be used to determine the hash. By using the cryptographic hashing we can address the content, and content gets immutable because if you change anything in the data, the cryptographic hash changes and the link will be different. Bitcoin uses cryptographic hashing, where every block points to the previous one if you modify the block, the hash will change and will make the block invalid.
  • Buterin [2017] (†818 s.v. "Merkle Trees"): A Merkle tree is a type of binary tree, composed of a set of nodes with a large number of leaf nodes at the bottom of the tree containing the underlying data, a set of intermediate nodes where each node is the hash of its two children, and finally a single root node, also formed from the hash of its two children, representing the "top" of the tree. The purpose of the Merkle tree is to allow the data in a block to be delivered piecemeal: a node can download only the header of a block from one source, the small part of the tree relevant to them from another source, and still be assured that all of the data is correct.
  • Pfeffer [2017] (†844 s.v. "ModifiedMerklePatriciaTree"): Merkle Patricia trees provide a cryptographically authenticated data structure that can be used to store all (key, value) bindings, although for the scope of this paper we are restricting keys and values to strings (to remove this restriction, just use any serialization format for other data types). They are fully deterministic, meaning that a Patricia tree with the same (key,value) bindings is guaranteed to be exactly the same down to the last byte and therefore have the same root hash, provide the holy grail of O(log(n)) efficiency for inserts, lookups and deletes, and are much easier to understand and code than more complex comparison-based alternatives like red-black trees.
  • Scaling Bitcoin [2017] (†845 s.v. "Merkle tree / Hash tree"): A tree constructed by hashing paired data (the leaves), then pairing and hashing the results until a single hash remains, the merkle root. In Bitcoin, the leaves are almost always transactions from a single block.

Citations

  • Wood 2014 (†803 p.17): The modified Merkle Patricia tree (trie) provides a persistent data structure to map between arbitrary-length binary data (byte arrays). It is defined in terms of a mutable data structure to map between 256-bit binary fragments and arbitrary-length binary data, typically implemented as a database. The core of the trie, and its sole requirement in terms of the protocol specification is to provide a single value that identifies a given set of key-value pairs, which may be either a 32 byte sequence or the empty byte sequence. It is left as an implementation consideration to store and maintain the structure of the trie in a manner the allows effective and efficient realisation of the protocol. (†2175)